package main

import (
	"container/list"
	"fmt"
	"sort"
)

// 测试单链表

type ListNode struct {
	value int
	next  *ListNode
}

func creatList(p **ListNode) int {
	var data, ret int
	data = 1
	var pHead, node, tmp *ListNode
	pHead = new(ListNode)
	if pHead == nil {
		ret = -1
	}
	tmp = pHead // 刚创建是应该被初始化了一个0

	for {
		node = new(ListNode)
		if node == nil {
			ret = -1
			fmt.Println("listnode creat error")
		}
		node.value = data
		tmp.next = node
		tmp = tmp.next
		data++
		if data == 6 {
			break
		}
	}
	node.next = nil
	*p = pHead
	return ret

}

func deleteNode(head *ListNode, val int) *ListNode {
	var pHead, pre, cur *ListNode
	pHead = head
	pre = pHead
	cur = head.next
	// printnode(pHead)
	// printnode(pre)
	// printnode(cur)
	if pre.value == val { // 头结点
		return cur
	}
	for cur != nil { // 中间节点 或尾节点
		if cur.value == val {
			pre.next = cur.next
		} else {
			pre = cur
		}
		cur = cur.next
	}
	// if cur.next == nil && cur.value == val { // 尾节点
	// 	pre.next = cur.next
	// 	pre = pre.next
	// 	return pHead
	// }
	return pHead
}

func printnode(head *ListNode) {
	for head != nil {
		fmt.Print(head.value)
		fmt.Print("->")
		head = head.next
	}
	fmt.Print("\n")
}

// 给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.
func getKthFromEnd(head *ListNode, k int) *ListNode {
	// 方法一两次遍历，第一次求倒数的k值，第二次返回链表
	nodeLen := lenNode(head)
	kk := nodeLen - k + 1
	i := 1
	for head.next != nil {
		if i == kk {
			return head
		}
		i++
		head = head.next

	}
	return head
}

// 求链表的长度
func lenNode(head *ListNode) int {
	ret := 0
	for head != nil {
		ret++
		head = head.next
	}
	fmt.Println("lenNode = ", ret)
	return ret
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
	// 利用栈重新创建一个链表
	p1Head := head
	p2Head := head
	l := list.New()
	for p1Head != nil {
		l.PushFront(p1Head.value) // 543210
		p1Head = p1Head.next
	}
	for i := l.Front(); i != nil; i = i.Next() {
		fmt.Println(i.Value)
		p2Head.value = i.Value.(int)
		p2Head = p2Head.next
	}
	return head
}
func reverseList2(head *ListNode) *ListNode {
	// 利用栈重新创建一个链表
	p1Head := head
	p2Head := head
	var arr []int
	for i := 0; p1Head != nil; i++ {
		arr = append(arr, p1Head.value)
		p1Head = p1Head.next
	}
	// 切片转数组

	for i := len(arr) - 1; i != 0; i-- {
		p2Head.value = arr[i]
		p2Head = p2Head.next
	}
	return head
}

func main() {

	a := []int{4, 6, 1, 2, 5, 7, 3}
	sort.Ints(a)
	fmt.Println(a)
	// fmt.Println("test ptr")
	// var node *ListNode
	// ret := creatList(&node)
	// if ret != 0 {
	// 	fmt.Println("error")
	// }

	// printnode(node)
	// //lenNode(node)

	// // 删除节点
	// // node = deleteNode(node, 5)
	// // fmt.Print("deleted:")
	// // printnode(node)
	// // node = getKthFromEnd(node, 6)
	// // printnode(node)
	// node = reverseList(node)
	// printnode(node)
}
